import java.util.Arrays;

/**
 * @author wangj881
 * @date 2024-12-02 10:05
 */
public class L53_2 {
    public static void main(String[] args) {
        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        int i = new Solution().maxSubArray(nums);
        System.out.println(i);
    }


    static class Solution {
        public int maxSubArray(int[] nums) {
            int result = Integer.MIN_VALUE;
            int[] dp = new int[nums.length];
            dp[0] = nums[0];
            for (int i = 1; i < nums.length; i++) {
                dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
            }
//            System.out.println(Arrays.toString(dp));
            for (int i : dp) {
                result = Math.max(i, result);
            }
            return result;
        }
    }

//    static class Solution {
//        public int maxSubArray(int[] nums) {
//            int result = Integer.MIN_VALUE;
//            int sum = 0;
//            for (int i = 0; i < nums.length; i++) {
//                sum += nums[i];
//                result = Math.max(result, sum);
//                if (sum < 0) {
//                    sum = 0;
//                }
//            }
//            return result;
//        }
//    }

//    static class Solution {
//        public int maxSubArray(int[] nums) {
//            int result = Integer.MIN_VALUE;
//            int sum = 0;
//            for (int j = 0; j < nums.length; j++) {
//                for (int i = j; i < nums.length; i++) {
//                    sum += nums[i];
//                    result = Math.max(result, sum);
//                }
//                sum = 0;
//            }
//            return result;
//        }
//    }
}
